/*
 * elevator noop
 */
#include <linux/blkdev.h>
#include <linux/elevator.h>
#include <linux/bio.h>
#include <linux/module.h>
#include <linux/slab.h>
#include <linux/init.h>
#include <linux/types.h>
#include <linux/time.h>
#include <linux/jiffies.h>

#define THRESHOLD 600

struct sswt_data {
	struct list_head queue;
	sector_t head_pos;
	unsigned long average_delay;
	unsigned long total_requests;
	unsigned long total_seek_distance;
};

static unsigned long get_distance(struct request *rq, struct sswt_data *sd)
{
	sector_t req_sector = blk_rq_pos(rq);
	if(sd->head_pos > req_sector)
		return sd->head_pos - req_sector;
	else
		return req_sector - sd->head_pos;
}

static void sswt_merged_requests(struct request_queue *q, struct request *rq,
				 struct request *next)
{
	list_del_init(&next->queuelist);
}

static void reorder_sswt_queue(struct sswt_data *sd)
{
	struct list_head *pos_prev, *pos_cur;
	struct request *rq, *cur_req;
	struct list_head prev_queue;
	struct list_head *mod_nodes;
	int is_inserted = 0;
	prev_queue.next = sd->queue.next;
	prev_queue.prev = sd->queue.prev;
	mod_nodes = sd->queue.next;
	mod_nodes->prev = &prev_queue;
	mod_nodes = sd->queue.prev;
	mod_nodes->next = &prev_queue;
	
	INIT_LIST_HEAD(&sd->queue);
	
	pos_prev = prev_queue.next;
	
	while(pos_prev != &prev_queue)
	{
		rq = list_entry(pos_prev, struct request, queuelist);
		pos_prev = pos_prev->next;
		INIT_LIST_HEAD(&rq->queuelist);
		is_inserted = 0;
		list_for_each(pos_cur, &sd->queue)
		{
			cur_req = list_entry(pos_cur, struct request, queuelist);
			if(get_distance(rq, sd) < get_distance(cur_req, sd))
			{
				list_add(&rq->queuelist, cur_req->queuelist.prev);
				is_inserted = 1;
				break;
				
			}
		}
		if(is_inserted == 0)
			list_add_tail(&rq->queuelist, &sd->queue);
	}
}

static void increment_counters(struct sswt_data *sd)
{
	struct list_head *pos;
	struct request *cur_req;
	list_for_each(pos, &sd->queue)
	{
		cur_req = list_entry(pos, struct request, queuelist);
		cur_req->wait_count++;
	}
}

static int sswt_dispatch(struct request_queue *q, int force)
{
	struct sswt_data *sd = q->elevator->elevator_data;
	long delay;
	struct list_head *pos;
	struct request *cur_req;
	struct request *max_wait_req;
	struct request *ss_rq;
	unsigned long max_wait_count = 0;
	struct timespec curr_time;
	
	//Average delay declarations
	unsigned long nsec_curr, nsec_rq;
	
	if (!list_empty(&sd->queue)) 
	{
		struct request *rq;
		list_for_each(pos, &sd->queue)
		{
			cur_req = list_entry(pos, struct request, queuelist);
			if(cur_req->wait_count > max_wait_count)
			{
				max_wait_count = cur_req->wait_count;
				max_wait_req = cur_req;
			}
		}
		if(max_wait_count > THRESHOLD)
		{	
			rq = max_wait_req;
			ss_rq = list_entry(sd->queue.next, struct request, queuelist);
			printk(KERN_INFO "\nRequest with sector %ld overriding shorter seek candidate with sector %ld", blk_rq_pos(rq), blk_rq_pos
							 (ss_rq));
		}
		else 
		{
			rq = list_entry(sd->queue.next, struct request, queuelist);		
		}

		
		list_del_init(&rq->queuelist);
		sd->head_pos = blk_rq_pos(rq) + blk_rq_sectors(rq);
	
		//Average Delay
		getnstimeofday(&curr_time);
		nsec_curr = curr_time.tv_sec * 1000000000 + curr_time.tv_nsec;
		nsec_rq = rq->arrival_time.tv_sec * 1000000000 + rq->arrival_time.tv_nsec; 
		delay = nsec_curr - nsec_rq;			  	         	   
	  
   		sd->average_delay += delay;
	   	sd->total_requests++;
	   	sd->total_seek_distance += get_distance(rq, sd);
	   
	    printk(KERN_INFO "\n[SSWT-START]");
		printk(KERN_INFO "\n Current time: Sec = %ld, Nanoseconds = %ld, Total Delay = %ld", curr_time.tv_sec, 
						curr_time.tv_nsec, sd->average_delay);
		printk(KERN_INFO "\n Arrival Time of request: Sec = %ld, Nanoseconds = %ld", rq->arrival_time.tv_sec, rq->arrival_time.tv_nsec);
		printk(KERN_INFO "\nTotal seek distance = %ld", sd->total_seek_distance);
		printk(KERN_INFO "\n Total Requests  = %ld", sd->total_requests);
		if(max_wait_count <= THRESHOLD)
		{
			printk(KERN_INFO "\nRequest for sector = %ld dispatched, Wait Count = %ld", blk_rq_pos(rq), rq->wait_count);
		}
		else
		{
			reorder_sswt_queue(sd);
			printk(KERN_INFO "\nRequest for sector = %ld dispatched Wait Count = %ld", blk_rq_pos(rq), rq->wait_count);
		}
		printk(KERN_INFO "\n[SSWT-END]");
		increment_counters(sd);	
		elv_dispatch_sort(q, rq);
		
		return 1;
	}
	return 0;
}


static void sswt_add_request(struct request_queue *q, struct request *rq)
{
	struct sswt_data *sd = q->elevator->elevator_data;
	struct list_head *pos;
	struct request *cur_req;
	
	//Average Delay
	getnstimeofday(&rq->arrival_time);
	
	//Set the wait counter
	rq->wait_count = 0;
	list_for_each(pos, &sd->queue)
	{
		cur_req = list_entry(pos, struct request, queuelist);
		if(get_distance(rq, sd) < get_distance(cur_req, sd))
		{
			list_add(&rq->queuelist, cur_req->queuelist.prev);
			return;
		}
	}
	list_add_tail(&rq->queuelist, &sd->queue);
}

static struct request *
sswt_former_request(struct request_queue *q, struct request *rq)
{
	struct sswt_data *sd = q->elevator->elevator_data;

	if (rq->queuelist.prev == &sd->queue)
		return NULL;
	return list_entry(rq->queuelist.prev, struct request, queuelist);
}

static struct request *
sswt_latter_request(struct request_queue *q, struct request *rq)
{
	struct sswt_data *sd = q->elevator->elevator_data;

	if (rq->queuelist.next == &sd->queue)
		return NULL;
	return list_entry(rq->queuelist.next, struct request, queuelist);
}

static int sswt_init_queue(struct request_queue *q)
{
	struct sswt_data *sd;

	sd = kmalloc_node(sizeof(*sd), GFP_KERNEL, q->node);
	if (!sd)
		return -ENOMEM;

	INIT_LIST_HEAD(&sd->queue);
	sd->head_pos = 0;
	sd->average_delay = 0;
	sd->total_requests = 0;
	sd->total_seek_distance = 0;
	q->elevator->elevator_data = sd;
	return 0;
}

static void sswt_exit_queue(struct elevator_queue *e)
{
	struct sswt_data *sd = e->elevator_data;

	BUG_ON(!list_empty(&sd->queue));
	kfree(sd);
}

static struct elevator_type elevator_sswt = {
	.ops = {
		.elevator_merge_req_fn		= sswt_merged_requests,
		.elevator_dispatch_fn		= sswt_dispatch,
		.elevator_add_req_fn		= sswt_add_request,
		.elevator_former_req_fn		= sswt_former_request,
		.elevator_latter_req_fn		= sswt_latter_request,
		.elevator_init_fn		= sswt_init_queue,
		.elevator_exit_fn		= sswt_exit_queue,
	},
	.elevator_name = "sswt",
	.elevator_owner = THIS_MODULE,
};

static int __init sswt_init(void)
{
	struct timeval tv;
	do_gettimeofday(&tv);
	
	printk(KERN_INFO "\nTime of day = %ld SSWT initialized", tv.tv_sec);
	return elv_register(&elevator_sswt);
}

static void __exit sswt_exit(void)
{
	printk(KERN_INFO "\nSSWT removed");
	elv_unregister(&elevator_sswt);
}

module_init(sswt_init);
module_exit(sswt_exit);


MODULE_AUTHOR("Rima And Shruti");
MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("SSWT IO scheduler");
